package com.shigi.knapsack.solvers;

import com.shigi.knapsack.KnapsackInstance;
import com.shigi.knapsack.KnapsackItem;
import com.shigi.knapsack.KnapsackSolution;
import com.shigi.knapsack.KnapsackSolver;

import java.util.Stack;

/**
 * Created by Miroslav Šiagi on 15/10/14.
 */
public class BranchBound implements KnapsackSolver {

    private KnapsackSolution knapsackSolution;
    private KnapsackInstance knapsackInstance;
    private KnapsackItem[] knapsackItems;

    public KnapsackSolution solve(KnapsackInstance knapsackInstance) {
        this.knapsackInstance = knapsackInstance;
        this.knapsackSolution = new KnapsackSolution(knapsackInstance.getId());
        this.knapsackSolution.setNumberOfItems(knapsackInstance.getNumberOfItems());
        this.knapsackItems = this.knapsackInstance.getKnapsackItems();

        int currentKnapsackValue = 0;
        int upperLimit = getTotalValueOfItems(this.knapsackItems);
        createSolution(upperLimit);

        this.knapsackSolution.setNumberOfItems(this.knapsackItems.length);
        return this.knapsackSolution;
    }

    private void createSolution(int upperLimit) {

        int n = this.knapsackItems.length;

        int W = this.knapsackInstance.getTotalWeight();
        int[] p = new int[n];
        int[] w = new int[n];

        for (int i = 0; i < n; i++) {
            p[i] = this.knapsackItems[i].getValue();
            w[i] = this.knapsackItems[i].getWeight();
        }

        this.knapsackSolution.setTotalValue(solverBranchAndBound(W, n, p, w, upperLimit));
    }

    public int solverBranchAndBound(int capacity, int itemCount, final int[] values, final int[] weights, int upperLimit) {
        Stack<BranchBoundState> stack = new Stack<BranchBoundState>();
        stack.add(new BranchBoundState(0, 0, 0, upperLimit));

        int maxValue = Integer.MIN_VALUE;
        int maxWeight = Integer.MIN_VALUE;

        while (!stack.isEmpty()) {
            BranchBoundState currentState = stack.pop();
            if (currentState.index >= itemCount) {
                if (currentState.value > maxValue) {
                    maxValue = currentState.value;
                    maxWeight = currentState.weight;
                }
                continue;
            }
            if (maxValue >= currentState.value + currentState.restSum) {
                continue;
            }
            if (currentState.weight + weights[currentState.index] <= capacity) {
                BranchBoundState branchBoundState =
                        new BranchBoundState(currentState.index + 1,
                                currentState.value + values[currentState.index],
                                currentState.weight + weights[currentState.index],
                                currentState.restSum - values[currentState.index]);

                stack.push(branchBoundState);
            }
            currentState.restSum -= values[currentState.index];
            currentState.index++;
            stack.push(currentState);
        }
        return maxValue;
    }



    private int getTotalValueOfItems(KnapsackItem[] knapsackItems) {
        int value = 0;
        for (int i = 0; i < knapsackItems.length; i++) {
            value += knapsackItems[i].getValue();
        }
        return value;
    }
}
